/**
 * 斐波那契数列
 * F(0) = 0，F(1) = 1
 * F(n) = F(n - 1) + F(n - 2)，其中 n > 1 
 **/

#include<iostream>

// Solution 1:递归，开销大容易栈溢出
class Solution {
public:
    int fib(int n) {
        if(n <= 2){
            return 1;
        }
        return fib(n-1) + fib(n-2);
    }
};

// Solution 2:

int main(){
    int x = 30;
    Solution s;
    int result = s.fib(x);
    std::cout<<result;
}